#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>

#define SIZE 1024

int open_file(char *filename, char *mode, FILE **fp, int must_exist);

/*Functions used to encode the strings.*/
void bw_c(char input[SIZE+1], int size, char output[SIZE+1], int *index);
void set_table(char table[][SIZE+1], char input[SIZE+1], int len);
void set_indices(int *indices);
void sort_table(char table[][SIZE+1], int start, int end, int indices[SIZE]);
void print_table(char table[][SIZE+1], int order[SIZE], int size);

/*Functions used to decode the strings.*/
void sort_string(char str[], int first, int last);
void compute_alphabet(char sorted[], int len, char alphabet[], int *size);
int binary_search(char alphabet[], int size, char c);
void bw_d(char coded[], int len, int index, char decoded[]);

int main(int argc, char **argv) {
  struct stat file_stat;
  FILE *ifp, *ofp;
  char *input_file, *output_file, buffer[SIZE+1], output[SIZE+1];
  char sorted[SIZE+1], alphabet[SIZE+1], decoded[SIZE+1];
  int output_index, symbol_count;
  size_t bytes_read;

  if (argc != 3) {
    printf("Usage: ./%s <input_file> <output_file>\n", argv[0]);
    exit(-1);
  }
  
  input_file = argv[1];
  output_file = argv[2];
  
  if (open_file(input_file, "r", &ifp, 1) == -1)
    exit(-1);
  
  if (open_file(output_file, "w", &ofp, 0) == -1)
    exit(-1);
  
  while (!feof(ifp)) {
    bytes_read = fread(buffer, 1, SIZE, ifp);
    
    if (bytes_read != SIZE) {
      if (ferror(ifp)) {
        printf("An error occurred while reading the input file.\n");
        clearerr(ifp);
        break;
      }
    }
    buffer[(int)bytes_read] = '\0';
    
    /*encode the chunk we just read.*/
    bw_c(buffer, (int)bytes_read, output, &output_index);
    
    /*decode and write to the output file.*/
    bw_d(output, (int)bytes_read, output_index, decoded);
    fwrite(decoded, 1, bytes_read, ofp);
  }
  
  fclose(ifp);
  fclose(ofp);

  return 0;
}

/**
  Opens a file with the provided filename and checks for errors.
  \param filename - Name of the file to be opened.
  \param mode - Must be "w" for writing mode or "r" for reading mode.
  \param fp - File pointer to the file. This will be NULL when the function 
  returns if there was an error while opening the file.
  \param must_exist - Either 1 or 0. Pass 1 if the file must exist; 0
  otherwise. Note that output files don't have to exist prior the running of
  the program, but input files do.
  \return -1 if an error occurred, 0 otherwise.
*/
int open_file(char *filename, char *mode, FILE **fp, int must_exist)
{
  struct stat file_stat;
  int status;
  
  printf("Opening %s...\n", filename);
  
  status = lstat(filename, &file_stat);
  if (must_exist && status == -1) {
    printf("File %s does not exist.\n", filename);
    return -1;
  }
  
  if (status == 0 && !S_ISREG(file_stat.st_mode)) {
    printf("File %s must be a regular file.\n", filename);
    return -1;
  }
  
  *fp = fopen(filename, mode);
  if (*fp == NULL) {
    printf("Unable to open file %s\n", filename);
    return -1;
  }
  rewind(*fp);

  printf("File %s opened successfully...\n", filename);
  return 0;
}

/**
  Computes the Burrows-Wheeler transform for the input string provided.
  \param input - String to be transformed.
  \param size - Size of the string to be transformed.
  \param output - String where the resulting transformation will be returned.
  \param index - Pointer to an integer where the output index of the BWT will
  be returned.
*/
void bw_c(char input[], int size, char output[], int *index)
{
  char table[SIZE][SIZE+1];
  int sorted_indices[SIZE], i;

  set_table(table, input, size);
  set_indices(sorted_indices);  
  sort_table(table, 0, size-1, sorted_indices);
  
  for (i = 0; i < size; ++i) {
    if (sorted_indices[i] == 0)
      *index = i;
    output[i] = table[sorted_indices[i]][size-1];
  }
  output[i] = '\0';
}

/**
  Sets the table used to do BWT.
  \param table - 2D array of char that represents the table.
  \param input - Input string to be encoded.
  \param len - actual lenght of the string. The string could have length up to
  SIZE, but it could be shorter than that.
*/
void set_table(char table[][SIZE+1], char input[SIZE+1], int len)
{
  int i, j;
  strcpy(table[0], input);
  for (i = 1; i < len; ++i) {
    table[i][0] = table[i-1][len-1];
    /*TODO: there must be a way to do this using memcpy; which should be
    faster.*/
    for (j = 1; j < len; ++j)
      table[i][j] = table[i-1][j-1];
    table[i][j] = '\0';
  }
}

/**
  Sets the values of the elements in the indices array equal to the index of
  the item.  Note that this function assumes that the indices array has the
  globally defined size.
  \param indices - Pointer to an array of integers.
*/
void set_indices(int *indices)
{
  int i;
  if (indices == NULL)
    return;
  for (i = 0; i < SIZE; ++i)
    indices[i] = i;
}

/**
  Sorts the rows in the table in lexicographical order using the merge sort
  algorithm.
  \param table - Table whose rows will be sorted.
  \param start - Integer representing index of first row that is being sorted.
  \param end - Integer representing the index of the last row that is being
  sorted.
  \param indices - Array of integers representing the order of the rows after 
  they are sorted.
*/
void sort_table(char table[][SIZE+1], int start, int end, int indices[SIZE])
{
  int temp_index, temp_indices[SIZE];
  int middle, right_count, left_count;
  int i, j, k;
  
  /*Only one element or no elements to sort.*/
  if (end <= start)
    return;
  
  /*Two elements to sort.*/
  if ((end - start) == 1) {
    if (strcmp(table[start], table[end]) > 0) {
      temp_index = indices[start];
      indices[start] = indices[end];
      indices[end] = temp_index;
    }
    return;
  }
  
  middle = (start + end) / 2;
  sort_table(table, start, middle, indices);
  sort_table(table, middle + 1, end, indices);
    
  left_count = middle - start + 1;
  right_count = end - middle;
  i = start;
  j = middle + 1;
  k = 0;  
  while (left_count > 0 && right_count > 0) {
    if (strcmp(table[indices[i]], table[indices[j]]) < 0) {
      temp_indices[k] = indices[i];
      --left_count;
      ++i;
    } else {
      temp_indices[k] = indices[j];
      --right_count;
      ++j;
    }
    ++k;
  }
  
  while (left_count > 0) {
    temp_indices[k] = indices[i];
    --left_count;
    ++i;
    ++k;
  }
  
  while (right_count > 0) {
    temp_indices[k] = indices[j];
    --right_count;
    ++j;
    ++k;
  }
  
  k = 0;
  for (i = start; i <= end; ++i) {
    indices[i] = temp_indices[k];
    ++k;
  }
}

/**
  Prints the BWT table in a certain order.  This function is for debugging
  purposes only.
  \param table - Table whose contents is to be printed.
  \param order - Array of integers representing the order in which the table
  rows should be printed.
  \param size - Number of rows to be printed; the table is not always full.
*/
void print_table(char table[][SIZE+1], int order[SIZE], int size)
{
  int i;
  for (i = 0; i < size; ++i) {
    printf("[%s]\n", table[order[i]]);
  }
}

/**
  Sorts the letters in a string in lexicographical order using merge sort. Note
  that the algorithm modifies the string and assumes that the first and last
  indexes passed in the parameters are valid.
  \param str - String whose characters will be sorted. The result will also be
  stored in this parameter.
  \param first - Index where the sorting is starting.
  \param last - Index where the sorting ends.
*/
void sort_string(char str[], int first, int last)
{
  int middle, i, j, k, left_count, right_count;
  char temp, temp_str[SIZE+1];
  
  /*Only one item or no items to sort.*/
  if (last <= first) {
    return;
  }
    
  /*Two items to sort*/
  if ((last - first) == 1) {
    if ((str[first] - '0') > (str[last] - '0')) {
      temp = str[last];
      str[last] = str[first];
      str[first] = temp;
    }
    return;
  }

  /*Divide the work.*/
  middle = (last + first) / 2;
  sort_string(str, first, middle);
  sort_string(str, middle+1, last);
  
  /*Merge the partial lists.*/
  left_count = middle - first + 1;
  right_count = last - middle;
  i = first;
  j = middle + 1;
  k = 0;
  
  while (left_count > 0 && right_count > 0) {
    if (str[i] < str[j]) {
      temp_str[k] = str[i];
      --left_count;
      ++i;
    } else {
      temp_str[k] = str[j];
      --right_count;
      ++j;
    }
    ++k;
  }
  
  while (left_count > 0) {
    temp_str[k] = str[i];
    --left_count;
    ++i;
    ++k;
  }
  
  while (right_count > 0) {
    temp_str[k] = str[j];
    --right_count;
    ++j;
    ++k;
  }
  
  k = 0;
  for (i = first; i <= last; ++i) {
    str[i] = temp_str[k];
    ++k;
  }
}

/**
  Computes the alphabet from a sorted string.
  \param sorted - Input string, sorted.
  \param len - Length of the input string.
  \param alphabet - String where the alphabet will be stored.
  \param size - Pointer to an integer where the number of symbols in the
  alphabet will be stored.
*/
void compute_alphabet(char sorted[], int len, char alphabet[], int *size)
{
  int i, j;
  
  alphabet[0] = sorted[0];
  j = 1;
  for (i = 1; i < len; ++i) {
    if (sorted[i] == alphabet[j-1])
      continue;
    alphabet[j] = sorted[i];
    ++j;
  }
  alphabet[j] = '\0';
  *size = j;
}

/**
  Searches for a character c in a sorted list.
  \param alphabet - Sorted list of characters.
  \param size - Number of symbols in the alphabet.
  \param c - Character to search for.
*/
int binary_search(char alphabet[], int size, char c)
{
  int min, max, mid;
  
  min = 0;
  max = size - 1;
  
  while (1) {
    mid = (min + max) / 2;
    if (c == alphabet[mid])
      return mid;
      
    if (c > alphabet[mid])
      min = mid + 1;
    else
      max = mid - 1;
      
    if (min > max)
      break;
  }
  
  return -1;
}

/**
  Decodes a string encoded using BW.
  \param coded - String coded in BW.
  \param len - Length of the string.
  \param index - Index from BWT.
  \param decoded - Location where the decoded string will be saved when the
  function is done.
*/
void bw_d(char coded[], int len, int index, char decoded[])
{
  char alphabet[SIZE+1], sorted[SIZE+1];
  int i, j, k, symbol_count, sum, C[SIZE], P[SIZE];
  
  for (i = 0; i < SIZE; ++i)
    C[i] = 0;
  
  strcpy(sorted, coded);
  sort_string(sorted, 0, len-1);
  compute_alphabet(sorted, len, alphabet, &symbol_count);
  
  for (i = 0; i < len; ++i) {
    j = binary_search(alphabet, symbol_count, coded[i]);
    P[i] = C[j];
    ++C[j];
  }
  
  sum = 0;
  for (i = 0; i < symbol_count; ++i) {
    sum += C[i];
    C[i] = sum - C[i];
  }
  
  i = index;
  for (j = len-1; j >= 0; --j) {
    k = binary_search(alphabet, symbol_count, coded[i]);
    decoded[j] = coded[i];
    i = P[i] + C[k];
  }
  decoded[len] = '\0';
}













